/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.NoSuchElementException;

/** Iterator that returns only strings within a given range. */
public class RangeIterator extends LexicographicalIterator {
	private LexicographicalIterator iterator;
	private int[] upperBound;
	private int[] next;
	private int currentLeftmostChanged;
	private int nextLeftmostChanged;
	/** Length of prefix that matches the upper bound. */
	private int upperBoundMatchLength;
	
	/** Constructor.
	 *  @param lowerBound Only strings >= this bound are returned. If null, then
	 *                    lower bound is disabled.
	 *  @param upperBound Only strings < this bound are returned. If null, then
	 *                    upper bound is disabled. 
	 */
	public RangeIterator(LexicographicalIterator iterator, int[] lowerBound, int[] upperBound) {
		if (lowerBound!=null) {
			iterator.skipByLowerBound(lowerBound);
		}
		this.iterator = iterator;
		this.upperBound = upperBound;
		this.upperBoundMatchLength = 0;
		this.currentLeftmostChanged = -1;
		this.nextLeftmostChanged = 0;
		if (iterator.hasNext()) next = iterator.next();
		checkUpperBound();
	}
	
	/** Checks if next is below upper bound. If not, next is set to null. */
	private void checkUpperBound() {
		if (upperBound==null) return;
		if (next==null) return;
		if (nextLeftmostChanged>upperBoundMatchLength) return;
		if (nextLeftmostChanged<upperBoundMatchLength) {
			next = null;
			return;
		}
		for (int i=nextLeftmostChanged; i<Math.min(next.length,upperBound.length); ++i) {
			if (next[i]==upperBound[i]) {
				upperBoundMatchLength+=1;
			} else {
				if (next[i]>upperBound[i]) next = null;
				return;
			}
		}
		if (next.length>=upperBound.length) next = null;
	}
	
	@Override
	public int getLeftmostChangedPosition() {
		return currentLeftmostChanged;
	}

	@Override
	public int[] peek() {
		if (next==null) throw new NoSuchElementException();
		return next;
	}

	@Override
	public void skip(int position) {
		if (nextLeftmostChanged>position) {
			iterator.skip(position);
			if (iterator.hasNext()) {
				next = iterator.next();
				nextLeftmostChanged = iterator.getLeftmostChangedPosition();
				checkUpperBound();
			} else {
				next = null;
				nextLeftmostChanged = -1;
			}
		}
	}

	@Override
	public boolean hasNext() {
		return next!=null;
	}

	@Override
	public int[] next() {
		if (next==null) throw new NoSuchElementException();
		int[] result = next;
		currentLeftmostChanged = nextLeftmostChanged;
		try {
			next = iterator.next();
			nextLeftmostChanged = iterator.getLeftmostChangedPosition();
		} catch (NoSuchElementException e) {
			next = null;
		}
		checkUpperBound();
		return result;
	}

	@Override
	public int getStringLength() {
		return iterator.getStringLength();
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

}
